COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	However, this text is %2not%* meant to be a programming manual for LISP.
C00008 00003	These notes are primarily designed for undergraduates and therefore
C00010 ENDMK
C⊗;
However, this text is %2not%* meant to be a programming manual for LISP.
A certain amount of time is spent giving insights into techniques for
writing LISP functions.  There are two reasons for this. First, the style
of LISP programming is quite different from that of "normal" programming.
Second, and more important, we will spend a great deal of time discussing
various levels of implementation of the language. LISP is an excellent
medium for introducing standard techniques such as recursion, garbage collection,
storage allocation, and hashing. It is pointless to attempt to discuss
implementation of a language which is poorly understood.

If the only reasons for learning a programming language were its applications,
then for most standard applications we could do better than LISP.  LISP
is at least fifteen years old and many languages now offer themselves with better
notation, more efficient running code, or larger varieties of data structure.
But the more interesting aspects of LISP for students of Computer Science lie
not in its features as a programming language, but in what it can show
about the about the %2structure%* of Computer Science. The application of
computers, as is hardware development, is peripheral to this field. There is a
rapidly expanding body of knowledge unique to Computer Science, neither
mathematical or engineering per se.  Much of this area is presented most
clearly by studying LISP.
As mentioned above, language implementors can learn much from LISP.  Indeed,
many of the "standard techniques" in language implementation (e.g. built-in
recursion, garbage collection) originated
with LISP. Many of the more theoretical areas of Computer Science 
(e.g. provability, semantics) can be
introduced using LISP. Many of the most interesting applications of computers
(e.g. artifical intelligence, game playing, theorem proving) 
have been done using LISP.

Much of the power of LISP lies in its simplicity. It is a"fixed point" in
non-numerical languages. The data structures are rich enough  to easily
describe sophisticated algorithms but not so rich as to become obfuscatory.
We will describe translators -- interpreters and compilers -- as very transparent
LISP functions.  Indeed the structure of the compilation process becomes so
transparent as to border on the trivial.  This is not to say that compiler writing
is trivial or even easy; but the structure of the process is easily seen.
This is partly due to the simplicity of the language, but perhaps more
due to our ability to go right to the compiling process without becoming
bogged down in details of scanners and parsers -- syntax--. Again, syntax
analysis is not trivial, but it is a peripheral activity to our understanding
of compilers and evaluators.

LISP is a better vehicle than its ancestor, the λ-calculus, because there is just enough
more complexity present in LISP to make its implementation a realistic 
Computer Science task and not just
an interesting mathematical curiosity. Most every aspect of the implementation
of LISP and its translators has immediate implications to the implementation of 
other languages and to the design of programming languages in
general.

LISP has very important implications in the field of programming language
semantics -- the meaning of languages--, also in a field of much current interest, 
provability of properties of programs.
These notes are primarily designed for undergraduates and therefore
an attempt is made to make them self-contained. 
There are basically four areas in which to distribute the topics covered:
the mechanics of the language, the evaluation of expressions in LISP,
the implementation of LISP, and the compilers for LISP. Each area
builds on the previous. Taken as a group these topics introduce 
much of what is interesting Computer Science.
The sooner LISP is mastered the better.

A large collection of problems has been included. The reader is urged to do as
many as possible.  The problems are mostly non-trivial; they attempt to be
realistic, introducing some new information which the readers should be
able to discover themselves. 

There are also a few rather substantial projects.  At least one should be attempted.
There is a significant difference between being able to program small problems
 and handle large projects. The increase in difficulty is exponential
rather than linear.